package c066;

/**
 * ClassName: c01
 * Package: c066
 * Description:
 * 509. 斐波那契数 https://leetcode.cn/problems/fibonacci-number/description/
 *
 * 0 <= n <= 30
 * @Author BCXJ
 * @Create 2025/11/30 23:00
 * @Version 1.0
 * @Since 1.0
 */
public class c01 {
    // 1 暴力方式
    // 11ms
    //击败13.22%
    public static int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;

        return fib(n - 1) + fib(n - 2);
    }

    // 2 傻缓存法
    /*
    执行用时分布
    0ms
    击败100.00%

     */
    static int[] cache = new int[30];
    public static int fib2(int n) {
        if(cache[n] != 0) return cache[n];
        if (n == 0) return 0;
        if (n == 1) return 1;
        cache[n] = fib2(n - 1) + fib2(n - 2);
        return cache[n];
    }

    // 傻缓存其实就是 至顶向下

    // dp 就是自底向上（需要找到对应的dp方程式）
    // 2 和 3方案的时间复杂度是一样的哦

    // 3 标准动态规划
    public static int fib3(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int[] dp = new int[n + 1];
        dp[0] = 0; dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

}
